class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        if nums[0] > 0:
            return result
        nums_len = len(nums)
        for i in range(0, nums_len-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            j, k = i+1, nums_len-1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s == 0:
                    result.append([nums[i], nums[j], nums[k]])
                    j += 1
                    k -= 1
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                    while j < k and nums[k] == nums[k+1]:
                        k -= 1
                elif s < 0:
                    j += 1
                elif s > 0:
                    k -= 1
        return result


s = Solution()
nums = [-1,0,1,2,-1,-4]
result = s.threeSum(nums)
print(result)

nums = [0,1,1]
result = s.threeSum(nums)
print(result)

nums = [0,0,0]
result = s.threeSum(nums)
print(result)
